{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Element After Decreasing and Rearranging"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maximumElementAfterDecrementingAndRearranging"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #减小和重新排列数组后的最大元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个正整数数组 <code>arr</code> 。请你对 <code>arr</code> 执行一些操作（也可以不进行任何操作），使得数组满足以下条件：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>arr</code> 中 <strong>第一个</strong> 元素必须为 <code>1</code> 。</li>\n",
    "\t<li>任意相邻两个元素的差的绝对值 <strong>小于等于</strong> <code>1</code> ，也就是说，对于任意的 <code>1 <= i < arr.length</code> （<strong>数组下标从 0 开始</strong>），都满足 <code>abs(arr[i] - arr[i - 1]) <= 1</code> 。<code>abs(x)</code> 为 <code>x</code> 的绝对值。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你可以执行以下 2 种操作任意次：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><strong>减小</strong> <code>arr</code> 中任意元素的值，使其变为一个 <strong>更小的正整数</strong> 。</li>\n",
    "\t<li><strong>重新排列</strong> <code>arr</code> 中的元素，你可以以任意顺序重新排列。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你返回执行以上操作后，在满足前文所述的条件下，<code>arr</code> 中可能的 <strong>最大值</strong> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>arr = [2,2,1,2,1]\n",
    "<b>输出：</b>2\n",
    "<b>解释：</b>\n",
    "我们可以重新排列 arr 得到 <code>[1,2,2,2,1] ，该数组满足所有条件。</code>\n",
    "arr 中最大元素为 2 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>arr = [100,1,1000]\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>\n",
    "一个可行的方案如下：\n",
    "1. 重新排列 <code>arr</code> 得到 <code>[1,100,1000] 。</code>\n",
    "2. 将第二个元素减小为 2 。\n",
    "3. 将第三个元素减小为 3 。\n",
    "现在 <code>arr = [1,2,3] ，满足所有条件。</code>\n",
    "arr 中最大元素为 3 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>arr = [1,2,3,4,5]\n",
    "<b>输出：</b>5\n",
    "<b>解释：</b>数组已经满足所有条件，最大元素为 5 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= arr.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 <= arr[i] <= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-element-after-decreasing-and-rearranging](https://leetcode.cn/problems/maximum-element-after-decreasing-and-rearranging/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-element-after-decreasing-and-rearranging](https://leetcode.cn/problems/maximum-element-after-decreasing-and-rearranging/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,2,1,2,1]', '[100,1,1000]', '[1,2,3,4,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        retVal = 1\n",
    "\n",
    "        arr.sort()\n",
    "        arrSize = len(arr)\n",
    "        for i in range(1, arrSize):\n",
    "            if arr[i] - retVal >= 1:\n",
    "                retVal += 1\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: list[int]) -> int:\n",
    "        arr.sort()\n",
    "        arr[0] = 1\n",
    "        for i in range(1, len(arr)):\n",
    "            if not abs(arr[i]-arr[i-1]) <= 1:\n",
    "                arr[i] = arr[i-1]+1\n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        limit = 1\n",
    "        for num in sorted(arr)[1:]:\n",
    "            limit = min(limit + 1, num)\n",
    "        return limit\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        t = 1\n",
    "        for x in arr:\n",
    "            if x < t:\n",
    "                continue\n",
    "            t+=1\n",
    "        return t-1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        arr[0], n = 1, len(arr)\n",
    "        for i in range(1, n):\n",
    "            if arr[i] - arr[i - 1] > 1:\n",
    "                arr[i] = arr[i - 1] + 1\n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        arr[0] = 1\n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[i] - arr[i - 1] > 1:\n",
    "                arr[i] = arr[i - 1] + 1\n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "\n",
    "        # 奇怪的題目...\n",
    "        \"\"\"\n",
    "        arr.sort()\n",
    "\n",
    "        # 第一個元素一定要等於 1\n",
    "        if arr[0] != 1:\n",
    "            arr[0] = 1\n",
    "\n",
    "        max_num = arr[0]\n",
    "        for i in range(1, len(arr)):\n",
    "            diff = abs(arr[i] - arr[i-1])\n",
    "            if diff <= 1:\n",
    "                max_num = max(max_num, arr[i])\n",
    "            else:\n",
    "                arr[i] = arr[i - 1] + 1\n",
    "                max_num = max(max_num, arr[i])\n",
    "        return max_num\n",
    "        \"\"\"\n",
    "        \n",
    "        # 比較簡潔的寫法\n",
    "        arr.sort()\n",
    "        max_num = arr[0] = 1\n",
    "\n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[i] - arr[i - 1] > 1:\n",
    "                arr[i] = arr[i - 1] + 1\n",
    "            max_num = max(max_num, arr[i])\n",
    "        return max_num "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        arr[0] = 1\n",
    "        for i in range(1, n):\n",
    "            arr[i] = min(arr[i - 1] + 1, arr[i])\n",
    "        return arr[n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        arr[0] = 1\n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[i] - arr[i-1] > 1:\n",
    "                arr[i] = arr[i-1] + 1\n",
    "        return arr[-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        limit=1\n",
    "        for i in sorted(arr)[1:]:\n",
    "            limit=min(limit+1,i)\n",
    "        return limit\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        index = 0\n",
    "        for i in arr:\n",
    "            if i > index:\n",
    "                index += 1\n",
    "        return index\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        retVal = 1\n",
    "\n",
    "        arr.sort()\n",
    "\n",
    "        arrSize = len(arr)\n",
    "        for i in range(1, arrSize):\n",
    "            if arr[i] - retVal >= 1:\n",
    "                retVal += 1\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        cnt = [False] + [True] * n\n",
    "        arr.sort()\n",
    "        i = 1\n",
    "        for x in arr:\n",
    "            if i <= x:\n",
    "                cnt[i] = True\n",
    "                i += 1\n",
    "        return i - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        # 不用考虑原数组元素，只需构造与原数组一样长度的新数组即可\n",
    "        n = len(arr)\n",
    "        arr.sort()\n",
    "        if arr[0] != 1:\n",
    "            arr[0] = 1\n",
    "        for i in range(1, n):\n",
    "            tm = arr[i]-arr[i-1]\n",
    "            if tm != 0:\n",
    "                arr[i] = arr[i-1] + 1\n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "\n",
    "        # 奇怪的題目...\n",
    "        \"\"\"\n",
    "        arr.sort()\n",
    "\n",
    "        # 第一個元素一定要等於 1\n",
    "        if arr[0] != 1:\n",
    "            arr[0] = 1\n",
    "\n",
    "        max_num = arr[0]\n",
    "        for i in range(1, len(arr)):\n",
    "            diff = abs(arr[i] - arr[i-1])\n",
    "            if diff <= 1:\n",
    "                max_num = max(max_num, arr[i])\n",
    "            else:\n",
    "                arr[i] = arr[i - 1] + 1\n",
    "                max_num = max(max_num, arr[i])\n",
    "        return max_num\n",
    "        \"\"\"\n",
    "        \n",
    "        # 比較簡潔的寫法\n",
    "        arr.sort()\n",
    "        max_num = arr[0] = 1\n",
    "\n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[i] - arr[i - 1] > 1:\n",
    "                arr[i] = arr[i - 1] + 1\n",
    "            max_num = max(max_num, arr[i])\n",
    "        return max_num "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "\n",
    "        arr.sort()\n",
    "\n",
    "        if arr[0] != 1:\n",
    "            arr[0] = 1\n",
    "\n",
    "        max_num = arr[0]\n",
    "        for i in range(1, len(arr)):\n",
    "            diff = abs(arr[i] - arr[i-1])\n",
    "            if diff <= 1:\n",
    "                max_num = max(max_num, arr[i])\n",
    "            else:\n",
    "                arr[i] = arr[i - 1] + 1\n",
    "                max_num = max(max_num, arr[i])\n",
    "        return max_num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        limit = 1\n",
    "        for num in arr[1:]:\n",
    "            limit = min(limit+1, num)\n",
    "        return limit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        ans = 0\n",
    "        for i in arr:\n",
    "            if i - ans > 1:\n",
    "                ans += 1\n",
    "            else:\n",
    "                ans = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        if arr[0] != 1:\n",
    "            arr[0] = 1\n",
    "        for i in range(1,len(arr)):\n",
    "            if arr[i] - arr[i - 1] > 1:\n",
    "                arr[i] = arr[i - 1] + 1\n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        arr[0] = 1\n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[i] - arr[i-1] > 1:\n",
    "                arr[i] = arr[i-1]+1\n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        if n==1:\n",
    "            return 1\n",
    "        arr.sort()\n",
    "        if arr[0]!=1:\n",
    "            arr[0] = 1\n",
    "        start = 1\n",
    "        while start<n:\n",
    "            if abs(arr[start]-arr[start-1])<=1:\n",
    "                start += 1\n",
    "            else:\n",
    "                arr[start] = arr[start-1]+1\n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        arr[0] = 1\n",
    "        for i in range(1, n):\n",
    "            if arr[i] - arr[i - 1] > 1:\n",
    "                arr[i] = arr[i - 1] + 1\n",
    "        return arr[n - 1] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        limit = 1\n",
    "        for num in sorted(arr)[1:]:\n",
    "            limit = min(limit + 1, num)\n",
    "        return limit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        retVal = 0\n",
    "\n",
    "        arr.sort()\n",
    "        retVal = 1\n",
    "\n",
    "        arrSize = len(arr)\n",
    "        for i in range(1, arrSize):\n",
    "            if arr[i] - retVal >= 1:\n",
    "                retVal += 1\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        counter = [0 for _ in range(len(arr)+1)]\n",
    "        for i, v in enumerate(arr):\n",
    "            if v >= len(counter):\n",
    "                v = len(counter)-1\n",
    "            counter[v] += 1\n",
    "        miss = 0\n",
    "        res = 0\n",
    "        for i in range(1, len(counter)):\n",
    "            v = counter[i]\n",
    "            if v == 0:\n",
    "                miss += 1\n",
    "            else:\n",
    "                if v > miss:\n",
    "                    miss = 0\n",
    "                    res = i\n",
    "                else:\n",
    "                    res += v\n",
    "                    miss -= v       \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        arr.sort()\n",
    "        arr[0] = 1\n",
    "        for i in range(n-1):\n",
    "            if arr[i+1] - arr[i] > 1:\n",
    "                arr[i+1] = arr[i] + 1\n",
    "        \n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        i = 1\n",
    "        n = len(arr)\n",
    "        arr[0] = 1\n",
    "        while i < n:\n",
    "            if arr[i] - arr[i-1] <= 1:\n",
    "                i += 1\n",
    "            else:\n",
    "                arr[i] = arr[i-1] + 1\n",
    "        return arr[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        arr.sort()\n",
    "        arr[0] = 1\n",
    "        for i in range(n-1):\n",
    "            if arr[i+1] - arr[i] > 1:\n",
    "                arr[i+1] = arr[i] + 1\n",
    "        \n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        arr.sort()\n",
    "        arr[0] = 1\n",
    "        for i in range(1, n):\n",
    "            if arr[i]>arr[i-1]:\n",
    "                arr[i] = arr[i-1] + 1\n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "\n",
    "        # 奇怪的題目...\n",
    "        \"\"\"\n",
    "        arr.sort()\n",
    "\n",
    "        # 第一個元素一定要等於 1\n",
    "        if arr[0] != 1:\n",
    "            arr[0] = 1\n",
    "\n",
    "        max_num = arr[0]\n",
    "        for i in range(1, len(arr)):\n",
    "            diff = abs(arr[i] - arr[i-1])\n",
    "            if diff <= 1:\n",
    "                max_num = max(max_num, arr[i])\n",
    "            else:\n",
    "                arr[i] = arr[i - 1] + 1\n",
    "                max_num = max(max_num, arr[i])\n",
    "        return max_num\n",
    "        \"\"\"\n",
    "        \n",
    "        # 比較簡潔的寫法\n",
    "        arr.sort()\n",
    "        max_num = arr[0] = 1\n",
    "\n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[i] - arr[i - 1] > 1:\n",
    "                arr[i] = arr[i - 1] + 1\n",
    "            max_num = max(max_num, arr[i])\n",
    "        return max_num "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "\n",
    "        # 奇怪的題目...\n",
    "        \"\"\"\n",
    "        arr.sort()\n",
    "\n",
    "        # 第一個元素一定要等於 1\n",
    "        if arr[0] != 1:\n",
    "            arr[0] = 1\n",
    "\n",
    "        max_num = arr[0]\n",
    "        for i in range(1, len(arr)):\n",
    "            diff = abs(arr[i] - arr[i-1])\n",
    "            if diff <= 1:\n",
    "                max_num = max(max_num, arr[i])\n",
    "            else:\n",
    "                arr[i] = arr[i - 1] + 1\n",
    "                max_num = max(max_num, arr[i])\n",
    "        return max_num\n",
    "        \"\"\"\n",
    "        \n",
    "        # 比較簡潔的寫法\n",
    "        arr.sort()\n",
    "        max_num = arr[0] = 1\n",
    "\n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[i] - arr[i - 1] > 1:\n",
    "                arr[i] = arr[i - 1] + 1\n",
    "            max_num = max(max_num, arr[i])\n",
    "        return max_num "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        arr[0] = 1\n",
    "        for i in range(1,n):\n",
    "            if arr[i] > arr[i-1] + 1:\n",
    "                arr[i] = arr[i-1] + 1\n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        limit = 1\n",
    "        for num in sorted(arr)[1:]:\n",
    "            limit = min(limit + 1, num)\n",
    "        return limit\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        arr.sort()\n",
    "        arr[0] = 1\n",
    "        for i in range(n-1):\n",
    "            if arr[i+1] - arr[i] > 1:\n",
    "                arr[i+1] = arr[i] + 1\n",
    "        \n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        arr.sort()\n",
    "        arr[0] = 1\n",
    "        for i in range(1, n):\n",
    "            if arr[i] - arr[i - 1] > 1:\n",
    "                arr[i] = arr[i - 1] + 1\n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "\n",
    "        # 奇怪的題目...\n",
    "        \"\"\"\n",
    "        arr.sort()\n",
    "\n",
    "        # 第一個元素一定要等於 1\n",
    "        if arr[0] != 1:\n",
    "            arr[0] = 1\n",
    "\n",
    "        max_num = arr[0]\n",
    "        for i in range(1, len(arr)):\n",
    "            diff = abs(arr[i] - arr[i-1])\n",
    "            if diff <= 1:\n",
    "                max_num = max(max_num, arr[i])\n",
    "            else:\n",
    "                arr[i] = arr[i - 1] + 1\n",
    "                max_num = max(max_num, arr[i])\n",
    "        return max_num\n",
    "        \"\"\"\n",
    "\n",
    "        # 比較簡潔的寫法\n",
    "        \"\"\"\n",
    "        arr.sort()\n",
    "        max_num = arr[0] = 1\n",
    "\n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[i] - arr[i - 1] > 1:\n",
    "                arr[i] = arr[i - 1] + 1\n",
    "            max_num = max(max_num, arr[i])\n",
    "        return max_num\n",
    "        \"\"\"\n",
    "\n",
    "        # 不用更改 arr 內容\n",
    "        arr.sort()\n",
    "        prev = 0\n",
    "        for i in arr:\n",
    "            prev = min(prev + 1, i)\n",
    "        return prev"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        arr[0] = 1\n",
    "        for i in range(1, len(arr)):\n",
    "            arr[i] = min(arr[i], arr[i-1] + 1)\n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        cur = 1\n",
    "        arr[0] = 1\n",
    "        for num in arr:\n",
    "            if num <= cur:\n",
    "                continue\n",
    "            else:\n",
    "                cur+=1\n",
    "        return cur"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        j = len(arr) - 1\n",
    "        for i, x in enumerate(arr):\n",
    "            if i >= j + 1: return i\n",
    "            if x < i + 1:\n",
    "                if j > i and arr[j] >= i + 1:\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    return i\n",
    "        return len(arr)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        if arr[0] != 1:\n",
    "            arr[0] = 1\n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[i] > arr[i - 1] + 1:\n",
    "                arr[i] = arr[i - 1] + 1\n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        base=0\n",
    "        for i,v in enumerate(arr):\n",
    "            if v>base:\n",
    "                base+=1\n",
    "        return base"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        arr.sort()\n",
    "        pre = 1\n",
    "        for i in range(1, n):\n",
    "            if arr[i] == pre:\n",
    "                continue\n",
    "            pre += 1\n",
    "        return pre \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        ideal = len(arr)\n",
    "        arr.sort()\n",
    "        gap = 0\n",
    "        # 核心在于查看当前数与1,2,3升序数组相差值gap为多少。这个gap直接影响到最终输出的最大值。\n",
    "        for i, v in enumerate(arr, 1):\n",
    "            gap = max(gap, i - v)\n",
    "        return ideal - gap\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        arr[0] = 1\n",
    "        for i in range(1,len(arr)) :\n",
    "            if arr[i] -1 > arr[i-1] :\n",
    "                arr[i] = arr[i-1] + 1\n",
    "            pass\n",
    "        return arr[-1]\n",
    "        pass"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        arr[0]=1\n",
    "        for i in range(1,len(arr)):\n",
    "            if arr[i]>arr[i-1]:\n",
    "                arr[i]=arr[i-1]+1\n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        arr.sort()\n",
    "        arr[0] = 1\n",
    "        for i in range(1, n):\n",
    "            arr[i] = min(arr[i - 1] + 1, arr[i])\n",
    "\n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        arr[0] = 1\n",
    "        for i in range(1, len(arr)) :\n",
    "            if arr[i] > arr[i-1]+1 :\n",
    "                arr[i] = arr[i-1]+1\n",
    "        \n",
    "        return arr[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        limit = 1\n",
    "        for num in sorted(arr)[1:]:\n",
    "            limit = min(limit + 1, num)\n",
    "        return limit\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        # limit = 1\n",
    "        # for num in sorted(arr)[1:]:\n",
    "        #     limit = min(limit + 1, num)\n",
    "        # return limit\n",
    "\n",
    "        #维护一个记录1到n分别有多少个的数组即可\n",
    "        #第一个循环是计数，统计arr里面从1到n每个数有多少个(大于n的统一看做n，因为答案最大才是n，再大的数也得减小到n); 第二个循环是从1到n搭建，对于第i个台阶，我们不可能超过它(因为每次变化最多为1)，该台阶能为limit做出的贡献有它的个数(这里主要是为了补足前面空缺的台阶)。比如说你有n个n，1到n-1一个没有，limit到最后一个循环仍然能取到n，这就好比用了n-1个n去补充前面的所有台阶的感觉，但是不管怎么填充，也不能超过自己的最高上限。这就好比你有100个1，和有1个1是一样的\n",
    "        n = len(arr)\n",
    "        cnts = [0] * (n + 1)\n",
    "        for num in arr:\n",
    "            cnts[min(num, n)] += 1\n",
    "        limit = 0\n",
    "        for i in range(1, n + 1):\n",
    "            #下一个台阶\n",
    "            limit = min(i, limit + cnts[i])\n",
    "        return limit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        arr[0]=1\n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[i]-arr[i-1]>1:\n",
    "                arr[i] = arr[i-1]+1\n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            ans = min(i + 1, arr[i], ans + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        \n",
    "        arr[0] = 1\n",
    "        for i in range(1, len(arr)):\n",
    "            if arr[i] >= arr[i - 1] + 1:\n",
    "                arr[i] = arr[i - 1] + 1\n",
    "\n",
    "        return arr[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        arr.sort()\n",
    "        arr[0] = 1\n",
    "        for i in range(1, n):\n",
    "            if arr[i] - arr[i - 1] > 1:\n",
    "                arr[i] = arr[i - 1] + 1\n",
    "        return arr[n - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        mx = max(arr)\n",
    "        arr.sort()\n",
    "        for i in range(n):\n",
    "            if i == 0:\n",
    "                arr[i] = 1\n",
    "            else:\n",
    "                if arr[i] - arr[i - 1] > 1:\n",
    "                    arr[i] = arr[i - 1] + 1\n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        arr[0]=1\n",
    "        for i in range(1,len(arr)):\n",
    "            arr[i]=min(arr[i-1]+1,arr[i])\n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        cnts = [0] * (len(arr) + 1)\n",
    "\n",
    "        for a in arr:\n",
    "            cnts[min(a, len(arr))] += 1\n",
    "\n",
    "        i = 1\n",
    "        j = 1\n",
    "\n",
    "        while True:\n",
    "            while j < len(cnts) and cnts[j] == 0:\n",
    "                j += 1\n",
    "            \n",
    "            if j == len(cnts):\n",
    "                break\n",
    "            \n",
    "            while j < len(cnts) and cnts[j] != 0 and i <= j:\n",
    "                i += 1\n",
    "                cnts[j] -= 1\n",
    "            \n",
    "            if j < len(cnts) and cnts[j] != 0 and i > j:\n",
    "                j += 1\n",
    "\n",
    "        return i - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        limit = 1\n",
    "        n = len(arr)\n",
    "        for i in range(1, n):\n",
    "            limit = min(limit + 1, arr[i])\n",
    "        return limit\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        N = len(arr)\n",
    "        cnts = [0 for _ in range(N + 1)]\n",
    "        for num in arr:\n",
    "            cnts[min(num, N)] += 1\n",
    "        \n",
    "        miss = 0\n",
    "        for idx in range(1, N + 1):\n",
    "            cnt = cnts[idx]\n",
    "            if cnt == 0:\n",
    "                miss += 1\n",
    "            else:\n",
    "                miss = max(0, miss - (cnt - 1)) # we can use (cnt - 1) nums to be decreased to fill the missing nums\n",
    "\n",
    "        return N - miss\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        n = len(arr)\n",
    "        if arr[0]!=1:\n",
    "            arr[0] = 1\n",
    "        for i in range(1,n):\n",
    "            if arr[i]-arr[i-1]>1:\n",
    "                arr[i] = arr[i-1]+1\n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr.sort()\n",
    "        arr[0] = 1\n",
    "\n",
    "        for i in range(1, len(arr)):\n",
    "            arr[i] = min(arr[i], arr[i-1] + 1)\n",
    "        \n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr = sorted(arr)\n",
    "        res = 1\n",
    "        l = len(arr)\n",
    "        prev = 0\n",
    "        for i in range(l):\n",
    "            if arr[i]>i+1 or arr[i]-prev>1:\n",
    "                arr[i] = min(i+1, prev+1)\n",
    "            prev = arr[i]\n",
    "            res = max(res, prev)\n",
    "            \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        a=[1]\n",
    "        for n in sorted(arr)[1:]:a.append(min(a[-1]+1,n))\n",
    "        return a[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        arr = sorted(arr)\n",
    "        arr[0] = 1\n",
    "        for i in range(1, len(arr)):\n",
    "            arr[i] = min(arr[i - 1] + 1, arr[i])\n",
    "        return arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        sort_arr = sorted(arr)\n",
    "        sort_arr[0]=1\n",
    "\n",
    "        for i in range(1,len(sort_arr)):\n",
    "            if sort_arr[i]-sort_arr[i-1] > 1:\n",
    "                sort_arr[i]=sort_arr[i-1]+1\n",
    "\n",
    "        return sort_arr[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maximumElementAfterDecrementingAndRearranging(self, arr: List[int]) -> int:\n",
    "        mapping = {}\n",
    "        for a in arr:\n",
    "            if(a not in mapping):\n",
    "                mapping[a] = 1\n",
    "            else:\n",
    "                mapping[a] += 1\n",
    "        nums = sorted(list(mapping.keys()))\n",
    "        curmax = 0\n",
    "        for num in nums:\n",
    "            if(mapping[num] >= num - curmax):\n",
    "                curmax = num \n",
    "            else:\n",
    "                curmax += mapping[num]\n",
    "        return curmax"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
